public class Solution96 {

    int[] f;

    public int numTrees(int n) {
        f=new int[n+1];
        f[0]=1;
        return dfs(n,f);
    }

    private int dfs(int n, int[] f) {
        if (f[n]!=0){
            return f[n];
        }
        for (int i=0;i<=n-1;i++){
            f[n]=f[n]+dfs(i,f)*dfs(n-i-1,f);
        }
        return f[n];
    }

    public static void main(String[] args) {
        System.out.println(new Solution96().numTrees(3));
    }
}
